package com.hackerrank.contests.july13.challenges.hackerranknumber;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class MultipleSolution {
	private static int numBits(int N) {
		int c = 0;
		while(N > 0) {
			c++;
			N >>= 1;
		}
		return c;
	}
	private static int numDigs(int N) {
		int c = 0;
		while(N > 0) {
			c++;
			N /= 10;
		}
		return c;
	}
	private static int LCM(int a, int b) {
		return a * b / GCF(a, b);
	}
	private static int GCF(int a, int b) {
		return GCFmm(Math.min(a, b), Math.max(a, b));
	}
	private static int GCFmm(int m, int M) {
		if(m == 0)
			return M;
		return GCFmm(M % m, m);
	}
	public static void main(String[] args) {
		for(int A = 1; A <= 30; A++) {
			for(int B = 1; B <= 75; B++) {
				BigInteger ls = BigInteger.ZERO, lc = BigInteger.ZERO, bb = new BigInteger(Integer.toString(B)), b2 = new BigInteger("2");
				for(int i = 1; i <= A; i++) {
					boolean a[] = new boolean[A + 1];
					List<Integer> l = new ArrayList<Integer>();
					List<Boolean> s = new ArrayList<Boolean>();
					BigInteger bi = new BigInteger(Integer.toString(i)), bip = new BigInteger(Integer.toString(i - 1));
					for(int j = i; j <= A; j++) {
						if(a[j])
							continue;
						int ni = l.size();
						BigInteger bj = new BigInteger(Integer.toString(j)), n = bi.multiply(bb).divide(bj), np = bip.multiply(bb).divide(bj);
						ls = ls.add(bj.multiply(n.multiply(n.add(BigInteger.ONE)).subtract(np.multiply(np.add(BigInteger.ONE)))).divide(b2));
						lc = lc.add(n.subtract(np));
						l.add(j);
						s.add(true);
						for(int k = 0; k < ni; k++) {
							int pn = l.get(k);
							boolean ps = s.get(k);
							int cn = LCM(j, pn);
							BigInteger bcn = new BigInteger(Integer.toString(cn));
							boolean cs = !ps;
							n = bi.multiply(bb).divide(bcn);
							np = bip.multiply(bb).divide(bcn);
							BigInteger v = bcn.multiply(n.multiply(n.add(BigInteger.ONE)).subtract(np.multiply(np.add(BigInteger.ONE)))).divide(b2);
							if(cs) {
								ls = ls.add(v);
								lc = lc.add(n.subtract(np));
							} else {
								ls = ls.subtract(v);
								lc = lc.subtract(n.subtract(np));
							}
							l.add(cn);
							s.add(cs);
						}
						for(int k = j; k <= A; k += j)
							a[k] = true;
					}
				}
				int C = (int)Math.pow(2, numBits(A)), X = B / C * C, U = B % C, ji = X == 0 ? 1 : 0;
				BigInteger rc = BigInteger.ZERO, rs = new BigInteger(Integer.toString(X)).multiply(new BigInteger(Integer.toString(X - 1))).divide(b2);
				Set<Integer> rl = new HashSet<Integer>();
				for(int i = 1; i <= A; i++)
					for(int j = ji; j <= U; j++)
						rl.add(i ^ j);
				for(int k : rl)
					rs = rs.add(new BigInteger(Integer.toString(X + k)));
				if(X <= 0 || A >= 2 && B >= 3 || A >= 3 && B >= 2)
					rc = new BigInteger(Integer.toString(X + rl.size()));
				else {
					rs = rs.subtract(BigInteger.ONE);
					rc = new BigInteger(Integer.toString(X + rl.size() - 1));
				}
				System.out.println("A: " + A + ", B: " + B);
				System.out.println("sa: " + ls + ", sb: " + rs);
				System.out.println(ls.multiply(rc).multiply(new BigInteger(Integer.toString((int)Math.pow(10, numDigs(B))))).add(rs.multiply(lc)));
			}
		}
	}
}
